其他
稀疏核机（中）—核方法
点击上方“大数据与人工智能”，“星标或置顶公众号”
第一时间获取好内容
作者丨stephenDC
这是作者的第7篇文章
在上一篇文章中，我们简单回顾了 SVM的导出 （点击加粗字体可回顾）。本篇文章将在此基础上，讨论SVM的基函数扩展，引出并重点讨论核方法。
在上一篇文章里介绍过，如果样本是线性不可分的，但在误差允许的范围内仍然适用线性模型，可以引入松弛变量来解决此类问题。
但如果样本不仅是线性不可分，而且线性分割的最优误差也完全无法接受，这时候就需要考虑扩充模型容量了。
不过，线性不可分的样本集，也许用抛物线（二阶多项式模型）就可分了，更不用说其他更加复杂的模型。而基函数扩展，是最常用的对线性模型进行容量扩展的方法之一，因此有理由期待，扩展后的SVM可以对数据集有更好的分类能力。
对线性模型进行基扩展，既可以提升模型容量，又可以直接类推线性模型的方法和结论，那么根据“没有免费午餐定理”，要付出的代价是什么呢？
先说答案：代价是计算量的增加。
引入核函数
显然，这种定义基于內积运算，且只是将基函数的內积，用一个二元函数代替而已。这当然是一种非常形式化的定义，后文会给出更加规范化的定义。
核函数定义
Mercer定理
Reproducing Kernel Hilbert Space
小结
核方法的引入，是为了在扩展模型容量的同时，不显著地增加计算量。原则上，在计算中只用到样本內积的模型，均可用核方法进行扩展。下一篇文章，我们会将核方法用到线性回归和感知器，并结合支持向量回归，来讨论稀疏性。
P.S.
很多文献里讲到，核方法是将输入空间的原问题，映射到高维（甚至无穷维）的特征空间中解决的。这种说法没有任何问题，但给人的感觉好像是，解决问题的关键是高维空间，到了高维空间很多问题都迎刃而解了。
事实上，解决问题的关键并不是将问题映射到了高维空间，而是非线性的映射本身。假设我们在原来p维的输入向量后面加上N个全是0的分量，那么显然即便N为无穷大，线性不可分的问题依然线性不可分。
但反过来，假设我们在映射前后并不增大（甚至减小）空间的维度，只要映射本身够复杂，依然可以解决问题（当然，这会过拟合）。
比如，三维空间中用平面不可分的数据集，我们总有办法人为的移动到二维空间中使之成为线性可分的数据集，而数据在移动前后的对应关系，即为所求的映射。
当然，这个映射必定会很复杂，如果用常规的基函数（比如多项式基函数）进行展开，基函数张成的空间也会是高维的。因此，相对于不同的基函数，可以视为将问题映射到了不同维度的空间，这只是看问题的一个角度，而非解决问题的实质所在。
以上部分是个人理解，欢迎交流意见，更欢迎批评指正。
参考文献
A Story of Basis and Kernel - Part I: Function Basis
A Story of Basis and Kernel - Part II: Reproducing Kernel Hilbert Space
核方法（1）-介绍
核方法（2）-核的性质
Mercer's theorem
The Elements of Statistical Learning
-end-